package com.company.剑指offer每日刷题.普通版;

/**
 * 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
 * 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
 * 示例：
 *
 * 输入：nums = [1,2,3,4]
 * 输出：[1,3,2,4]
 * 注：[3,1,2,4] 也是正确的答案之一。
 * 提示：
 *
 * 0 <= nums.length <= 50000
 * 0 <= nums[i] <= 10000
 * */
public class Exchange {
    /**
     * 方法：双指针法
     * 思路：
     *      1.定义左右两个left,right
     *      2.当left所在元素是奇数时，left ++；当right 所在元素是偶数时，right--；同时保证left < right
     *      3.将移动后的left 和right所在元素的值进行互换
     *      4.当left >= right时，返回nums
     * 优化： 判断奇偶性的写法，nums[i]%2!=0 等价于  nums[i]&1 == 1  ,位运算效率更高
     * */
    public int[] exchange(int[] nums) {
        int left =0,right = nums.length -1;
        while(left < right){
            while((nums[left]&1) == 1 && left < right)left++;
            while ((nums[right]&1) == 0 && left < right) right--;
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
        return nums;
    }
}
